package com.klun.project.common.constans.leetcode;
//给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。
//
// 示例：
// 输入：[1,2,3,4,5,null,7,8]
//
//        1
//       /  \
//      2    3
//     / \    \
//    4   5    7
//   /
//  8
//
//输出：[[1],[2,3],[4,5,7],[8]]
//
// Related Topics 树 广度优先搜索 链表 二叉树
// 👍 80 👎 0

import com.klun.project.common.constans.entity.ListNode;
import com.klun.project.common.constans.entity.TreeNode;
import com.klun.project.common.constans.utils.ParseUtils;

import java.util.HashMap;
import java.util.Map;

public class Solution0403 {

	private Map<Integer, ListNode> map;

	public ListNode[] listOfDepth(TreeNode node) {
		map = new HashMap<>();
		dfs(node, 0);
		ListNode[] lns = new ListNode[map.size()];
		int floor = 0;
		while (true) {
			ListNode ln = map.get(floor);
			if (ln == null) {
				return lns;
			}
			lns[floor] = ln;
			floor++;
		}
	}

	public void dfs(TreeNode node, int floor) {
		if (node == null) return;
		if (null == map.get(floor)) {
			map.put(floor, new ListNode(node.val));
		} else {
			ListNode a = map.get(floor);
			while (a.next != null) {
				a = a.next;
			}
			a.next = new ListNode(node.val);
		}
		int temp = floor;
		dfs(node.left, ++floor);
		floor = temp;
		dfs(node.right, ++floor);
	}

	public static void main(String[] args) {
		Solution0403 solution = new Solution0403();
//		List<List<Integer>> arrayLists = ParseUtils.stringToIntLists("[[2],[3,4],[6,5,7],[4,1,8,3]]");
		TreeNode treeNode = ParseUtils.ArrayToBTree("[1,2,3,4,5,null,7,8]");
		ListNode[] listNodes = solution.listOfDepth(treeNode);
		System.out.println(listNodes);
	}
}
